package DynamicProgrammingPackage;

public class findTargetSumWays_ {

    // 将集合分成正数集合 和 负数集合
    // 争取正数总和 + 负数总和 = target
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (Math.abs(target) > sum){
            return 0;
        }
        if ((sum + target) % 2 != 0){
            return 0;
        }
        // 1. dp[j] 表示 装满容量为j的背包有dp[j]种方法
        // 2. 递推公式: dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i])
        // 3. 初始化: dp[0] = 1,dp[*] = 0;
        // 4. 遍历顺序: 从前到后遍历

        // 之前都是问 给出容量能不能装满, 现在问有几种方式能装满
        int bagSize = (sum + target) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j- nums[i]];
            }
        }
        return dp[bagSize];
    }
}
